package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 17:48 2020/8/8
 * @Description  重建二叉树
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.TreeMap;

public class BuildTree {
    /**
     * 这道题的精髓就是每一次根都是先序确认的，然后由中序确定它的左右子树，一直递归，最后返回root
     *
     * @param preorder 先序序列
     * @param inorder  中序序列
     * @return
     */
    int[] pre; //将pre全局化
    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.pre = preorder;
        // 加快查找index速度
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recurBuild(0, 0, inorder.length - 1);
    }

    private TreeNode recurBuild(int preOrder_root_index, int inOrder_left, int inOrder_right) {
        if (inOrder_left>inOrder_right) return null;//说明中间区间没有元素，也就是没有节点了
        Integer index = map.get(pre[preOrder_root_index]);
        TreeNode root = new TreeNode(pre[preOrder_root_index]);
        //因为左子树第一个节点（如果有）就一定紧挨着root   右边界不能超过index-1  中序（左 中 右 ） 左为中（index）-1
        root.left = recurBuild(preOrder_root_index + 1, inOrder_left, index - 1);
        // index + 1 - inOrder_left + 1  这个就是左子树节点长度，右子树的root就是跳过左子树节点长度的第一个节点
        root.right = recurBuild(preOrder_root_index + index  - inOrder_left + 1, index + 1, inOrder_right);
        return root;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
